package com.example.leetdemo.finash;

public class Solution2405 {

    public int partitionString(String s) {
        int[] greed = new int[s.length() + 1];
        greed[0] = 0; greed[1] = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    greed[i + 1] = greed[j + 1] + 1;
                    break;
                }
                if (greed[j + 1] > greed[j]) {
                    greed[i + 1] = greed[j] + 1;
                    break;
                }
            }
        }
        return greed[s.length()];
    }

    public static void main(String[] args) {
        Solution2405 solution2405 = new Solution2405();
        System.err.println(solution2405.partitionString("abacaba"));
    }
}
